package com.zang.backtrack;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 递增子序列
 * @author ZVerify
 * @since 2022/11/15 11:27
 * @see <a href="https://leetcode.cn/problems/increasing-subsequences/description/">...</a>
 **/
public class 递增子序列 {

    // 结果集
    List<List<Integer>> result = new ArrayList<>();
    // 中间结果
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {

        backtrack(nums,0);
        return result;
    }

    private void backtrack(int[] nums, int startIndex) {
        // 当前不为一个值的时候就添加，因为在进入之前就已经进行了剪枝所以可以直接添加
        if (list.size() >1) {
            result.add(new ArrayList<>(list));
        }

        // 字典，因为我们此时要树层剪枝,但是当前不是有序的，因为要考虑递增所以不能排序要用set
        HashSet<Integer> set = new HashSet<>();

        for (int i = startIndex; i < nums.length; i++) {
            // 如果当前集合为null说明是第一个数据直接添加
            // 不为null的时候判断该层有没有出现过或者当前的值有没有上一个值大
            // 因为这里考虑了如果相同大小的数字的话也是相同的所以不加等于
            if (!list.isEmpty() && nums[i] < list.get(list.size() - 1) || set.contains(nums[i])) continue;
            set.add(nums[i]);
            list.add(nums[i]);
            // 递归
            backtrack(nums, i + 1);
            // 回溯
            list.remove(list.size() - 1);
        }

    }

}
